题意

给定 $n$ 行 $m$ 列的 $01$ 矩阵，求满足 $\big(\sum_{\forall i \in A, j \in B} value_{i, j}\big) \equiv 0 \pmod{2}$ 的二元组的数量

题解

首先考虑 $n = 1$，令 $1$ 的个数为 $t$，可以发现答案
$$
\sum\limits_{k = 0}^{\lfloor\frac{m}{2}\rfloor} \dbinom{t}{2k} \times 2^{m - t} - 1 = 2^{m - 1} - 1
$$
至于证明，可以考虑已经选好的数列 $\{a_1, a_2, …, a_n\}$，那么现在考虑加入第 $n +1$ 个，显然加入 $0, 1$ 都是多了两种选择

那么现在考虑将行合并成一列

但是问题是如果需要枚举选的行还是需要 $2^n$ 的复杂度，然后我考场上就想到这就凉了

那么显然每次选好了行，再选列的时候这若干个列会贯穿所有行，那就可以将每行看作一个数，并且将它们合并（异或）起来，这样就变成做 $n = 1$ 的情况了

接下来只要考虑有几种情况会使得其异或和为 $1$ （或不为 $1$）就行了

将它们求线性基，因为表示基的行向量不可能组成 $0$，故异或和为 $0$ 的情况就是 $2^{\text{所有的零向量个数}}$

令所有零向量个数为 $k$，那么答案即为 $(2^k - 1)(2^m - 1) + (2^n - 2^k)(2^{m - 1} - 1)$

然后高斯消元再用 $bitset$ 维护一下就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <cstdio>
#include <cstring>
#include <bitset>

#define MOD 998244353

using namespace std;

typedef long long LL;

const int MAXN = 2000 + 10;

LL power (LL x, int p) {
	LL cnt = 1;
	while (p) {
		if (p & 1)
			cnt = cnt * x % MOD;
		x = x * x % MOD;
		p >>= 1;
	}
	return cnt;
}

int N, M;
bitset<MAXN> bit[MAXN];

int Guass () {
	int row, col;
	for (row = 1, col = 1; row <= N && col <= M; row ++, col ++) {
		for (int i = row + 1; i <= N; i ++)
			if (bit[i][col])
				swap (bit[row], bit[i]);
		if (! bit[row][col]) {
			row --;
			continue;
		}
		for (int i = row + 1; i <= N; i ++)
			if (bit[i][col])
				bit[i] ^= bit[row];
	}
	row --;
	return N - row;
}

int getnum () {
	int num = 0;
	char ch = getchar ();
	while (! isdigit (ch))
		ch = getchar ();
	while (isdigit (ch))
		num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return num;
}

int main () {
	freopen ("password.in", "r", stdin);
	freopen ("password.out", "w", stdout);

	N = getnum (), M = getnum ();
	for (int i = 1; i <= N; i ++)
		for (int j = 1; j <= M; j ++) {
			int p = getnum ();
			bit[i][j] = p;
		}
	int zero = Guass ();
	LL ans = ((power (2ll, zero) - 1 + MOD) % MOD * ((power (2ll, M) - 1 + MOD) % MOD) % MOD +
			 (power (2ll, N) - power (2ll, zero) + MOD) % MOD * ((power (2ll, M - 1) - 1 + MOD) % MOD) % MOD) % MOD;
	cout << ans << endl;

	return 0;
}

/*
2 2
0 0
0 1
*/

/*
3 3
1 1 0
0 1 0
1 0 1
*/